// File:       bitset.c++
// Version:    1.00
// Author:     (c) Miles Sabin, 1996
// Purpose:    ANSI C++ bitset template

// Change log:
//   4/01/97   v. 1.00

#include "bitset.h"

#include <limits.h>
#include "string.h"


// Implementation of bitset<N>

template<size_t N>
bitset<N>::bitset(string const& str, size_t pos, size_t n)
  {
    reset();

    size_t rlen = str.size()-pos;
    if(rlen > n)
      rlen = n;
    if(rlen > N)
      rlen = N;

    for(size_t i = 0; i < rlen; ++i)
      if(str[pos+rlen-i-1] == '1')
        set(i);
  }

#if 0

template<size_t N>
size_t bitset<N>::count() const
  {
    size_t result = 0;

    for(int i = 0; i < (N+31)>>5; ++i)
    {
      int word = int(array_[i]);
      while(word != 0)
      {
        ++result;
        word &= ~-word;     // clear lsb
      }
    }

    return result;
  }

#else

template<size_t N>
size_t bitset<N>::count() const
  {
    size_t result = 0;

    for(int i = 0; i < (N+31)>>5; ++i)
    {
      unsigned long word = array_[i];

      word = (word&0x55555555)+((word>>1)&(0x55555555));
      word = (word&0x33333333)+((word>>2)&(0x33333333));
      word = (word&0x07070707)+((word>>4)&(0x07070707));
      word = (word&0x000F000F)+((word>>8)&(0x000F000F));
      word = (word&0x0000001F)+((word>>16)&(0x0000001F));
      result += int(word);
    }

    return result;
  }

#endif

template<size_t N>
bool bitset<N>::any() const
  {
    for(int i = 0; i < (N+31)>>5 && array_[i] == 0; ++i);
    return i != (N+31)>>5;
  }

template<size_t N>
bitset<N> bitset<N>::operator<<(size_t pos) const
  {
    bitset<N> tmp(*this);
    return tmp <<= pos;
  }

template<size_t N>
bitset<N> bitset<N>::operator>>(size_t pos) const
  {
    bitset<N> tmp(*this);
    return tmp >>= pos;
  }

template<size_t N>
bitset<N> bitset<N>::operator~() const
  {
    bitset<N> tmp(*this);
    return tmp.flip();
  }

template<size_t N>
bool bitset<N>::operator==(bitset<N> const& rhs) const
  {
    for(int i = 0; i < (N+31)>>5 && array_[i] == rhs.array_[i]; ++i);
    return i == (N+31)>>5;
  }

template<size_t N>
bitset<N>& bitset<N>::operator&=(bitset<N> const& rhs)
  {
    for(int i = 0; i < (N+31)>>5; ++i)
      array_[i] &= rhs.array_[i];

    return *this;
  }

template<size_t N>
bitset<N>& bitset<N>::operator|=(bitset<N> const& rhs)
  {
    for(int i = 0; i < (N+31)>>5; ++i)
      array_[i] |= rhs.array_[i];

    return *this;
  }

template<size_t N>
bitset<N>& bitset<N>::operator^=(bitset<N> const& rhs)
  {
    for(int i = 0; i < (N+31)>>5; ++i)
      array_[i] ^= rhs.array_[i];

    return *this;
  }

template<size_t N>
bitset<N>& bitset<N>::operator<<=(size_t pos)
  {
    if(pos > N)
      return reset();

    if(pos >= 32)
    {
      size_t word_shift = pos>>5;

      int i = ((N+31)>>5)-1;
      for(; i >= word_shift; --i)
        array_[i] = array_[i-word_shift];

      while(i >= 0)
        array_[i--] = 0;

      pos &= 31;
    }

    if(pos != 0)
    {
      unsigned long carry_in = 0;

      for(int i = 0; i < (N+31)>>5; ++i)
      {
        unsigned long carry_out = array_[i] >> (32-pos);
        array_[i] <<= pos;
        array_[i] |= carry_in;
        carry_in = carry_out;
      }

      clear_overflow();
    }

    return *this;
  }

template<size_t N>
bitset<N>& bitset<N>::operator>>=(size_t pos)
  {
    if(pos > N)
      return reset();

    if(pos >= 32)
    {
      size_t word_shift = pos>>5;

      int i = 0;
      size_t limit = ((N+31)>>5)-word_shift;
      for(; i < limit; ++i)
        array_[i] = array_[i+word_shift];

      while(i < (N+31)>>5)
        array_[i++] = 0;

      pos &= 31;
    }

    if(pos != 0)
    {
      unsigned long carry_in = 0;

      for(int i = (N+31)>>5; i > 0;)
      {
        --i;
        unsigned long carry_out = array_[i] << (32-pos);
        array_[i] >>= pos;
        array_[i] |= carry_in;
        carry_in = carry_out;
      }

      clear_overflow();
    }

    return *this;
  }

template<size_t N>
bitset<N>& bitset<N>::set()
  {
    for(int i = 0; i < (N+31)>>5; ++i)
      array_[i] = ULONG_MAX;

    clear_overflow();

    return *this;
  }

template<size_t N>
bitset<N>& bitset<N>::reset()
  {
    for(int i = 0; i < (N+31)>>5; ++i)
      array_[i] = 0;

    return *this;
  }

template<size_t N>
bitset<N>& bitset<N>::flip()
  {
    for(int i = 0; i < (N+31)>>5; ++i)
      array_[i] = ~array_[i];

    clear_overflow();

    return *this;
  }

template<size_t N>
string bitset<N>::to_string() const
  {
    string s;
    for(size_t i = N; i > 0;)
      s += (test(--i) ? '1' : '0');

    return s;
  }

template<size_t N>
void bitset<N>::clear_overflow()
  {
    if((N&31) != 0)
    {
      unsigned long mask = 0xffffffff<<(N&31);
      array_[((N+31)>>5)-1] &= ~mask;
    }
  }


// Implementation of bitset_reference<N>

template<size_t N>
bitset_reference<N>::bitset_reference(bitset<N>& base, size_t pos)
  : base_(base),
    pos_(pos)
  {}

